package com.jhy.review.day01;

import com.jhy.review.Binarytree.Tree;


import java.util.LinkedList;
import java.util.Queue;

/**
 * 完全二叉树
 * 宽度遍历
 * （1）每一个节点有右孩子，没有左孩子就返回FALSE
 * （2）如果一旦出现左右孩子不双全的时刻，且不违反第一个规定。接下来遇到的所有的节点都是叶子节点，就是完全二叉树。
 * 2022年7月20日21:48:39
 */
public class CompletelyBinaryTree {
    public static boolean CBT(Tree tree) {
        if (tree == null) {
            return true;
        }

        // 首先创建一个队列
        Queue<Tree> queue = new LinkedList<>();
        // 将头节点先放入队列当中
        queue.add(tree);
        // 声明一个开关 标志一旦出现左右孩子不双全的情况 且不会违反有右无左的情况
        boolean flag = false;
        // 声明左右子树
        Tree l = null;
        Tree r = null;
        while (!queue.isEmpty()) {
            Tree head = queue.poll();
            l = head.left;
            r = head.right;

            if (
                    // 有右孩子但是没有左孩子那么一定不是完全二叉树
                    l == null && r != null
                            ||
                            // 如果遇到了不双全的节点之后 又发现当前节点居然有孩子
                            (flag && (l != null || r != null))

            ){
                return false;
            }

            if (l != null) {
                queue.add(l);
            }
            if (r != null) {
                queue.add(r);
            }
            //  如果左边为空 或者右边为空 那么flag为true 就一直为ture了
            //  （1）当前为叶子节点，左右都为空
            //  （2）当前左不空右空，后面都为叶子节点
            //   (3) 左空右不空就不是完全二叉树了 前面就会判断就放回false
            if (l == null || r == null) {
                flag = true;
            }
        }
        return true;
    }
}
